package majorityElement;

public class Solution {
    public int majorityElement(int[] nums) {
        // 摩尔投票法
        int ans = nums[0],time = 1;
        for (int i = 1; i < nums.length; i++) {
            if( nums[i] == ans ) {
                time ++;
            }else {
                time--;
            }
            if(time == 0) {
                ans = nums[i];
                time = 1;
            }
        }
        time = 0;
        for (int i = 0; i < nums.length; i++) {
            if(ans == nums[i]) {
                time++;
            }
        }
        return time*2>nums.length?ans:-1;
    }
}
